package 第五周;

/*
 * @author  YxinMiracle
 * @date  2022-05-03 21:47
 * @Gitee: https://gitee.com/yxinmiracle
 */

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class 合并区间 {

    public int[][] merge(int[][] intervals) {
        List<Pair<Integer, Integer>> list = new ArrayList<>();
        PriorityQueue<Pair<Integer, Integer>> priorityQueue = new PriorityQueue<>(new Comparator<Pair<Integer, Integer>>() {
            @Override
            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                if (o1.getKey().equals(o2.getKey())){
                    return o1.getValue() - o2.getValue();
                }else {
                    return o1.getKey() - o2.getKey();
                }
            }
        });

        for (int[] interval : intervals) {
            int left = interval[0];
            int right = interval[1];
            priorityQueue.add(new Pair<>(left,1));
            priorityQueue.add(new Pair<>(right+1,-1));
        }

        int covering = 0;
        int start = 0;
        int end;
        while (!priorityQueue.isEmpty()){
            Pair<Integer, Integer> pair = priorityQueue.poll();
            if (covering == 0){
                start = pair.getKey();
            }
            covering += pair.getValue();
            if (covering == 0){
                end = pair.getKey()-1;
                list.add(new Pair<>(start,end));
            }
        }

        int total = list.size();
        int[][] result = new int[total][];
        for (int i = 0; i < total; i++) {
            result[i] = new int[]{list.get(i).getKey(),list.get(i).getValue()};
        }

        return result;

    }


}
